package com.lixianbiao;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 二叉树中序遍历
 *
 * @author lixianbiao
 * @since 2024/06/04 14:35
 */
public class InTraversal {
    // 二叉树节点
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 二叉树中序遍历的递归实现
     *
     * @param root
     * @return java.util.List<java.lang.Integer>
     * @author lixianbiao
     * @since 2024/04/20 8:48
     */
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        inorderTraversalRecursion(root, result);
        return result;
    }

    /**
     * 二叉树中序遍历的递归实现
     *
     * @param root
     * @param result
     * @return void
     * @author lixianbiao
     * @since 2024/04/20 8:50
     */
    private static void inorderTraversalRecursion(TreeNode root, List<Integer> result) {
        if (root != null) {
            inorderTraversalRecursion(root.left, result);//左子树
            result.add(root.val);//输出当前节点
            inorderTraversalRecursion(root.right, result);//右子树
        }
    }

    public static List<Integer> inorderTraversalMorris(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode preNode = null;
        while (root != null) {
            // 当前节点的左子树为空，输出该节点，访问该节点的右子树
            if (root.left == null) {
                list.add(root.val);
                root = root.right;
                continue;
            }
            // 寻找当前节点的中序前驱节点preNode
            preNode = root.left;
            while (preNode.right != null && preNode.right != root) {
                preNode = preNode.right;
            }
            // 当前节点有左子树，且中序前驱节点未记录线索，说明第一次访问该节点，所以记录线索标记，继续访问左子树
            if (preNode.right == null) {
                preNode.right = root; // 标记线索
                root = root.left; // 继续访问左子树
                continue;
            }
            // 当前节点有左子树，且中序前驱节点已记录线索。说明第二次访问该节点，所以取消线索，继续访问该节点的右子树
            list.add(root.val);
            preNode.right = null;
            root = root.right;
        }
        return list;
    }

    public static void main(String[] args) {
        // 创建一个简单的二叉树
        //       1
        //      / \
        //     2   3
        //    / \  /
        //   4   5 6
        TreeNode tree = new TreeNode(1);
        tree.left = new TreeNode(2);
        tree.right = new TreeNode(3);
        tree.left.left = new TreeNode(4);
        tree.left.right = new TreeNode(5);
        tree.right.left = new TreeNode(6);
        List<Integer> inOrder = inorderTraversalMorris(tree);
        System.out.println("inOrder = " + inOrder);
    }

}